import java.util.ArrayList;
import java.util.PriorityQueue;

//合并K个有序链表
// 测试链接：https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
public class MergeKSortedLists {
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static void main(String[] args) {

    }
    public static ListNode mergeKLists(ArrayList<ListNode> arr) {
        //创建小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a,b) -> a.val - b. val);
        //将所有头节点先全部放入优先级队列
        for(ListNode cur : arr) {
            if(cur != null) {
                heap.add(cur);
            }
        }
        //判断是否为空
        if(heap.isEmpty()) {
            return null;
        }
        //将小根堆头部弹出作为返回的头节点
        ListNode head = heap.poll();
        ListNode cur = head;
        if(cur.next != null) {
            heap.add(head.next);
        }

        while(!heap.isEmpty()) {
            cur.next = heap.poll();
            if(cur.next.next != null) {
                heap.add(cur.next.next);
            }
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }

}
